「Luogu P3569」[POI2014]KAR-Cards 解题报告

题面

前言

又是毒瘤翻译题，看了半天没看懂

贴上翻译

有 $n$ 张卡牌，每张卡牌正反两面都有数字。现进行 $m$ 次操作，每次操作会将两张卡牌的位置互换，问每次操作后能否通过翻转任意数量的卡牌，使得正面数字构成的序列不下降。

解题思路

线段树

分析

显然，$n$ 和 $m$ 的范围分别在 $2\times 10^5$ 和 $1\times 10^6$ 的级别，因此肯定能用线段树维护

考虑如何维护

令当前区间为 $[l,r]$，中点为 $m$，显然只有 $[l,m]$ 和 $[m+1,r]$ 单调不降，且 $m$ 号位上的树小于 $m+1$ 号位上的数，$[l,r]$ 区间才能是单调区间，因此可以开三维数组 $f[k][0/1][0/1]$ 表示区间左端点和右端点是否翻转的情况，然后分别从四种中间情况转移过来

贴个 Update

inline void Update(rint k,rint ls,rint m) {
    f[k][0][0]=(f[ls][0][0]&&b[m].fr<=b[m+1].fr&&f[ls|1][0][0])||
        (f[ls][0][0]&&b[m].fr<=b[m+1].bc&&f[ls|1][1][0])||
        (f[ls][0][1]&&b[m].bc<=b[m+1].fr&&f[ls|1][0][0])||
        (f[ls][0][1]&&b[m].bc<=b[m+1].bc&&f[ls|1][1][0]);
    f[k][0][1]=(f[ls][0][0]&&b[m].fr<=b[m+1].fr&&f[ls|1][0][1])||
        (f[ls][0][0]&&b[m].fr<=b[m+1].bc&&f[ls|1][1][1])||
        (f[ls][0][1]&&b[m].bc<=b[m+1].fr&&f[ls|1][0][1])||
        (f[ls][0][1]&&b[m].bc<=b[m+1].bc&&f[ls|1][1][1]);
    f[k][1][0]=(f[ls][1][0]&&b[m].fr<=b[m+1].fr&&f[ls|1][0][0])||
        (f[ls][1][0]&&b[m].fr<=b[m+1].bc&&f[ls|1][1][0])||
        (f[ls][1][1]&&b[m].bc<=b[m+1].fr&&f[ls|1][0][0])||
        (f[ls][1][1]&&b[m].bc<=b[m+1].bc&&f[ls|1][1][0]);
    f[k][1][1]=(f[ls][1][0]&&b[m].fr<=b[m+1].fr&&f[ls|1][0][1])||
        (f[ls][1][0]&&b[m].fr<=b[m+1].bc&&f[ls|1][1][1])||
        (f[ls][1][1]&&b[m].bc<=b[m+1].fr&&f[ls|1][0][1])||
        (f[ls][1][1]&&b[m].bc<=b[m+1].bc&&f[ls|1][1][1]);
}

以 f[k][0][1] 为例

f[k][0][1] 表示该区间左端点不翻转，右端点翻转，

然后枚举分出来的两段区间的左右端情况，即可转移

f[ls][0][1]&&b[m].bc<=b[m+1].fr&&f[ls|1][0][1] 表示两段区间首尾分别不翻和翻，两段分别单调且连接后仍单调，则 f[k][0][1] 可构成单调不降序列

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 200003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,T,l,pos;
struct node{
    int fr,bc;
    inline void input() {fr=read(),bc=read();}
}b[N],x,y;
bool f[N<<2][2][2];
inline void Update(rint k,rint ls,rint m) {//转移，分4种情况，可以写成for
    f[k][0][0]=(f[ls][0][0]&&b[m].fr<=b[m+1].fr&&f[ls|1][0][0])||
        (f[ls][0][0]&&b[m].fr<=b[m+1].bc&&f[ls|1][1][0])||
        (f[ls][0][1]&&b[m].bc<=b[m+1].fr&&f[ls|1][0][0])||
        (f[ls][0][1]&&b[m].bc<=b[m+1].bc&&f[ls|1][1][0]);
    f[k][0][1]=(f[ls][0][0]&&b[m].fr<=b[m+1].fr&&f[ls|1][0][1])||
        (f[ls][0][0]&&b[m].fr<=b[m+1].bc&&f[ls|1][1][1])||
        (f[ls][0][1]&&b[m].bc<=b[m+1].fr&&f[ls|1][0][1])||
        (f[ls][0][1]&&b[m].bc<=b[m+1].bc&&f[ls|1][1][1]);
    f[k][1][0]=(f[ls][1][0]&&b[m].fr<=b[m+1].fr&&f[ls|1][0][0])||
        (f[ls][1][0]&&b[m].fr<=b[m+1].bc&&f[ls|1][1][0])||
        (f[ls][1][1]&&b[m].bc<=b[m+1].fr&&f[ls|1][0][0])||
        (f[ls][1][1]&&b[m].bc<=b[m+1].bc&&f[ls|1][1][0]);
    f[k][1][1]=(f[ls][1][0]&&b[m].fr<=b[m+1].fr&&f[ls|1][0][1])||
        (f[ls][1][0]&&b[m].fr<=b[m+1].bc&&f[ls|1][1][1])||
        (f[ls][1][1]&&b[m].bc<=b[m+1].fr&&f[ls|1][0][1])||
        (f[ls][1][1]&&b[m].bc<=b[m+1].bc&&f[ls|1][1][1]);
}
inline void built(rint k,rint l,rint r) {//初始化
    if(l==r) return f[k][0][0]=f[k][1][1]=1,void();
    rint m=(l+r)>>1,ls=k<<1;
    built(ls,l,m),built(ls|1,m+1,r),Update(k,ls,m);
}
inline void Modify(rint k,rint l,rint r) {//修改
    if(l==r) return b[l]=y,void();
    rint m=(l+r)>>1,ls=k<<1;
    (pos<=m)?Modify(ls,l,m):Modify(ls|1,m+1,r);Update(k,ls,m);
}
int main()
{
    rint i,j;n=read();
    for(i=1;i<=n;i++) b[i].input();
    built(1,1,n),T=read();
    while(T--) {
        x=b[pos=read()],y=b[l=read()];//交换当成两次修改操作...
        Modify(1,1,n),y=x,pos=l,Modify(1,1,n);
        if(f[1][0][0]||f[1][0][1]||f[1][1][0]||f[1][1][1]) printf("TAK\n");
        else printf("NIE\n");//对整个区间首尾讨论一下
    }
    return 0;
}